package bst

// 节点
type node struct {
	val   int
	left  *node
	right *node
	level int
}

type BST struct {
	root *node
	size int
}

func NewBST() *BST {
	return &BST{
		root: nil,
		size: 0,
	}
}

func (bst *BST) Add(val int) {
	bst.root = bst.add(bst.root, val, 0)
}

func (bst *BST) add(root *node, val int, level int) *node {
	if root == nil {
		root = &node{
			val:   val,
			level: level + 1,
		}
		return root
	}

	if val < root.val {
		root.left = bst.add(root.left, val, root.level)
	}

	if val > root.val {
		root.right = bst.add(root.right, val, root.level)
	}

	return root
}

func (bst *BST) Size() int {
	return bst.size
}

// 前序遍历
// op func(int) 遍历的值的操作函数
// useRecursive 是否使用递归的方式实现
func (bst *BST) PreTravel(op func(int), useRecursive bool) {
	if useRecursive {
		preTravel(bst.root, op)
	}
}

func preTravel(root *node, op func(int)) {
	if root == nil {
		return
	}
	op(root.val)
	preTravel(root.left, op)
	preTravel(root.right, op)
}

// 中序遍历
// 对于二分搜索树来说，中序遍历会将从小到大依次打印数据
func (bst *BST) MidTravel(op func(int), useRecursive bool) {
	if useRecursive {
		midTravel(bst.root, op)
	}
}

func midTravel(root *node, op func(int)) {
	if root == nil {
		return
	}
	midTravel(root.left, op)
	op(root.val)
	midTravel(root.right, op)
}

// 后序遍历
func (bst *BST) PostTravel(op func(int), useRecursive bool) {
	if useRecursive {
		postTravel(bst.root, op)
	}
}

func postTravel(root *node, op func(int)) {
	if root == nil {
		return
	}
	postTravel(root.left, op)
	postTravel(root.right, op)
	op(root.val)
}

// 层序遍历
func (bst *BST) LevelTravel(op func(int, int), useRecursive bool) {
	if useRecursive {
		queue := make([]*node, 0)
		queue = append(queue, bst.root)
		for len(queue) > 0 {
			node := queue[0]
			op(node.val, node.level)
			queue = queue[1:]
			if node.left != nil {
				queue = append(queue, node.left)
			}
			if node.right != nil {
				queue = append(queue, node.right)
			}
		}
	}
}

func (bst *BST) Remove(val int) (bool, error) {
	return false, nil
}
